LeetCode 20、有效的括号

一、题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

• 1、左括号必须用相同类型的右括号闭合。
• 2、左括号必须以正确的顺序闭合。

二、题目解析

有效的括号满足以下几个条件：

• 1、字符串的长度一定是偶数。
• 2、括号的匹配遵循右括号和最近的一个左括号进行匹配，它们匹配成功才有可能是有效的括号

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的括号（ LeetCode 20 ）:https://leetcode-cn.com/problems/valid-parentheses
class Solution {
    
    public boolean isValid(String s) {
      
        // 当字符串长度为奇数的时候，属于无效情况，直接返回 false
  if (s.length() % 2 == 1) {
             // 无效情况，返回 false
       return false;
    }
       
     //构建一个栈，用来存储括号
        Stack<Character> stack = new Stack<Character>();
        
        // 把字符串转换为数组的形式，方便获取字符串中的每个字符
        char charArray[] = s.toCharArray();
        
        // 遍历字符串数组中的所有元素
        for( int i = 0 ; i < charArray.length ; i++){
            
            // 获取此时的字符
            char c = charArray[i];   
            
            // 如果字符为左括号 ( ，那么就在栈中添加对左括号 （
            if(c == '('){
               
               // 添加对左括号 （
               stack.push('(');

             // 如果字符为左括号 [ ，那么就在栈中添加对左括号 [
            }else if(c == '['){

               // 添加对应的右括号 ]
               stack.push('[');

             // 如果字符为左括号 { ，那么就在栈中添加对左括号 {
            }else if( c == '{'){

               // 添加对应的右括号 }
               stack.push('{');

               // 否则的话，说明此时 c 是 ）] } 这三种符号中的一种
            }else {
               
               // 如果栈已经为空，而现在遍历的字符 c 是 ）] } 这三种符号中的一种
               // 找不到可以匹配的括号，返回 false
               // 比如这种情况  }{，直接从右括号开始，此时栈为空
               if(stack.isEmpty()) return false;
               
               // 如果栈不为空，获取栈顶元素
               char top = stack.peek();

               // 将栈顶元素和此时的元素 c 进行比较，如果相同，则将栈顶元素移除
               if( top == '(' && c == ')' || top == '[' && c == ']' || top == '{' && c == '}' ){
                   // 移除栈顶元素
                   stack.pop();
               }else{
                   // 如果不相同，说明不匹配，返回 false
                   return false;
               }
 
            }

        }
        
        // 遍历完整个字符数组，判断栈是否为空
        // 如果栈为空，说明字符数组中的所有括号都是闭合的
        // 如果栈为空，说明有未闭合的括号
        return stack.isEmpty();
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的括号（ LeetCode 20 ）:https://leetcode-cn.com/problems/valid-parentheses
class Solution {
public:
    bool isValid(string s) {
        // 当字符串长度为奇数的时候，属于无效情况，直接返回 false
        if (s.size() % 2 == 1) {
             // 无效情况，返回 false
             return false;
        }
       
        //构建一个栈，用来存储括号
        stack<char> stk ;
        
        // 遍历字符串数组中的所有元素
        for( int i = 0 ; i < s.size() ; i++){
            
            // 获取此时的字符
            char c = s[i];   
            
            // 如果字符为左括号 ( ，那么就在栈中添加对左括号 （
            if(c == '('){
               
               // 添加对左括号 （
               stk.push('(');

             // 如果字符为左括号 [ ，那么就在栈中添加对左括号 [
            }else if(c == '['){

               // 添加对应的右括号 ]
               stk.push('[');

             // 如果字符为左括号 { ，那么就在栈中添加对左括号 {
            }else if( c == '{'){

               // 添加对应的右括号 }
               stk.push('{');

               // 否则的话，说明此时 c 是 ）] } 这三种符号中的一种
            }else {
               
               // 如果栈已经为空，而现在遍历的字符 c 是 ）] } 这三种符号中的一种
               // 找不到可以匹配的括号，返回 false
               // 比如这种情况  }{，直接从右括号开始，此时栈为空
               if(stk.empty()) return false;
               
               // 如果栈不为空，获取栈顶元素
               char top = stk.top();

               // 将栈顶元素和此时的元素 c 进行比较，如果相同，则将栈顶元素移除
               if( top == '(' && c == ')' || top == '[' && c == ']' || top == '{' && c == '}' ){
                   // 移除栈顶元素
                   stk.pop();
               }else{
                   // 如果不相同，说明不匹配，返回 false
                   return false;
               }
 
            }

        }
        
        // 遍历完整个字符数组，判断栈是否为空
        // 如果栈为空，说明字符数组中的所有括号都是闭合的
        // 如果栈为空，说明有未闭合的括号
        return stk.empty();

    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# // 有效的括号（ LeetCode 20 ）:https://leetcode-cn.com/problems/valid-parentheses
class Solution:
    def isValid(self, s: str) -> bool:
        # 当字符串长度为奇数的时候，属于无效情况，直接返回 False
        if len(s) % 2 == 1:
             # 无效情况，返回 False
             return False
        
       
        # 构建一个栈，用来存储括号
        stack = list()

        
        # 遍历字符串数组中的所有元素
        for c in s : 
            
            # 如果字符为左括号 ( ，那么就在栈中添加对左括号 （
            if c == '(' :
               
               # 添加对左括号 （
               stack.append('(')

             # 如果字符为左括号 [ ，那么就在栈中添加对左括号 [
            elif c == '[' :

               # 添加对应的右括号 ]
               stack.append('[')

             # 如果字符为左括号 { ，那么就在栈中添加对左括号 {
            elif c == '{' :

               # 添加对应的右括号 }
               stack.append('{')

               # 否则的话，说明此时 c 是 ）] } 这三种符号中的一种
            else :
               
               # 如果栈已经为空，而现在遍历的字符 c 是 ）] } 这三种符号中的一种
               # 找不到可以匹配的括号，返回 False
               # 比如这种情况  }{，直接从右括号开始，此时栈为空
               if not stack : 
                  return False
               
               # 如果栈不为空，获取栈顶元素
               top = stack[-1]

               # 将栈顶元素和此时的元素 c 进行比较，如果相同，则将栈顶元素移除
               if (top == '(' and c == ')' ) or (top == '[' and c == ']' ) or (top == '{' and c == '}')  :
                    # 移除栈顶元素
                    stack.pop()
               else :
                   # 如果不相同，说明不匹配，返回 False
                   return False

        
        # 遍历完整个字符数组，判断栈是否为空
        # 如果栈为空，说明字符数组中的所有括号都是闭合的
        # 如果栈为空，说明有未闭合的括号
        return not stack

四、复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，|Σ| =6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。